{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flatten Binary Tree to Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #linked-list #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #链表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flatten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树展开为链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根结点 <code>root</code> ，请你将它展开为一个单链表：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>展开后的单链表应该同样使用 <code>TreeNode</code> ，其中 <code>right</code> 子指针指向链表中下一个结点，而左子指针始终为 <code>null</code> 。</li>\n",
    "\t<li>展开后的单链表应该与二叉树 <a href=\"https://baike.baidu.com/item/%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86/6442839?fr=aladdin\" target=\"_blank\"><strong>先序遍历</strong></a> 顺序相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg\" style=\"width: 500px; height: 226px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,5,3,4,null,6]\n",
    "<strong>输出：</strong>[1,null,2,null,3,null,4,null,5,null,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点数在范围 <code>[0, 2000]</code> 内</li>\n",
    "\t<li><code>-100 <= Node.val <= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以使用原地算法（<code>O(1)</code> 额外空间）展开这棵树吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flatten-binary-tree-to-linked-list](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flatten-binary-tree-to-linked-list](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5,3,4,null,6]', '[]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: TreeNode):\n",
    "        \n",
    "        # Array containing all the nodes in the sorted order\n",
    "        self.nodes_sorted = []\n",
    "        \n",
    "        # Pointer to the next smallest element in the BST\n",
    "        self.index = -1\n",
    "        \n",
    "        # Call to flatten the input binary search tree\n",
    "        self._inorder(root)\n",
    "        \n",
    "    def _inorder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self._inorder(root.left)\n",
    "        self.nodes_sorted.append(root.val)\n",
    "        self._inorder(root.right)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        \"\"\"\n",
    "        @return the next smallest number\n",
    "        \"\"\"\n",
    "        self.index += 1\n",
    "        return self.nodes_sorted[self.index]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        \"\"\"\n",
    "        @return whether we have a next smallest number\n",
    "        \"\"\"\n",
    "        return self.index + 1 < len(self.nodes_sorted)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Tuple\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def myFlatten(self, head: 'Node') -> Tuple['Node']:\n",
    "        if head is None:\n",
    "            return (None, None)\n",
    "\n",
    "        p: 'Node' = head.prev\n",
    "        q: 'Nonde' = head\n",
    "        \n",
    "        while q is not None:\n",
    "            if q.child is not None:\n",
    "                dh, dt = self.myFlatten(q.child)\n",
    "                if q.next is not None:\n",
    "                    q.next.prev = dt\n",
    "                dt.next = q.next\n",
    "                dh.prev = q\n",
    "                q.next = dh\n",
    "                q.child = None\n",
    "                q = dt\n",
    "\n",
    "            p, q = q, q.next\n",
    "\n",
    "        return (head, p)\n",
    "\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        return self.myFlatten(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        walker = head\n",
    "        stack = []\n",
    "        while walker or stack:\n",
    "            if walker.child != None:\n",
    "                tmp = walker.next\n",
    "                if tmp:\n",
    "                    stack.append(tmp)\n",
    "                \n",
    "                child = walker.child\n",
    "                walker.next = child\n",
    "                child.prev = walker\n",
    "                walker.child = None\n",
    "            else:\n",
    "                if walker.next is None and stack:\n",
    "                    tmp = stack.pop()\n",
    "                    walker.next = tmp\n",
    "                    tmp.prev = walker\n",
    "                    #walker.next.prev = walker\n",
    "            walker = walker.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        list_res = []\n",
    "        def preOrder(root):\n",
    "            if not root:return None\n",
    "\n",
    "            list_res.append(root.val)\n",
    "            if root.child:\n",
    "                preOrder(root.child)\n",
    "            if root.next:\n",
    "                preOrder(root.next)\n",
    "        preOrder(head)\n",
    "        start = Node(0, None, None, None)\n",
    "        res = start\n",
    "        for each in list_res:\n",
    "            # print(each)\n",
    "            start.next = Node(each, start, None, None)\n",
    "            start = start.next\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        p = res = Node(None, None, None, None)\n",
    "        visited = head and [head]\n",
    "        while visited:\n",
    "            vertex = visited.pop()\n",
    "            if vertex.next:\n",
    "                visited.append(vertex.next)\n",
    "            if vertex.child:\n",
    "                visited.append(vertex.child)\n",
    "            p.next = vertex\n",
    "            p, p.prev, p.child = p.next, p, None\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head == None: return head\n",
    "        p, tail, stack = head, head, []\n",
    "        while p:\n",
    "            tail = p\n",
    "            if p.child:\n",
    "                if p.next: stack.append(p.next)\n",
    "                p.next = p.child\n",
    "                p.child.prev = p\n",
    "                p.child = None     \n",
    "            p = p.next\n",
    "            \n",
    "            if p: continue # p不为空执行上面的逻辑\n",
    "            if len(stack) > 0:\n",
    "                p = stack.pop()\n",
    "                tail.next = p\n",
    "                p.prev = tail\n",
    "                \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = [head]\n",
    "        pre = None\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "                node.child = None\n",
    "            if pre:\n",
    "                node.prev = pre\n",
    "                pre.next = node\n",
    "            pre = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        node = head\n",
    "        while node:\n",
    "            if node.child:\n",
    "                if node.next: # 如果存在 next 部分\n",
    "                    stack.append(node.next) # 就保存\n",
    "                node.child.prev = node # 让 node.child 变成 node.next\n",
    "                node.next = node.child # 同上\n",
    "                node.child = None # 置空 node.child\n",
    "            elif (not node.next) and stack: # 如果走到底没有next了，就把之前保存的 next 拿出来\n",
    "                last_next = stack.pop() # stack里最后一个就是最新的 next\n",
    "                node.next = last_next # 让它，变成当前 node 的 next\n",
    "                last_next.prev = node\n",
    "                \n",
    "            node = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        stack =[]\n",
    "        pa = head\n",
    "        while pa:\n",
    "            if pa.child:\n",
    "                if pa.next:\n",
    "                    stack.append(pa.next)\n",
    "                pa.child.prev = pa\n",
    "                pa.next = pa.child\n",
    "                pa.child = None\n",
    "                pa = pa.next\n",
    "            else:\n",
    "                if pa.next:\n",
    "                    pa.child = None\n",
    "                    pa.next.prev = pa\n",
    "                    pa = pa.next\n",
    "                if not pa.next:\n",
    "                    pa.child = None\n",
    "                    if stack:\n",
    "                        pa.next = stack.pop()\n",
    "                        pa.next.prev = pa\n",
    "                        pa = pa.next\n",
    "                    else:\n",
    "                        pa = pa.next\n",
    "                        break\n",
    "        return head\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        h = Node(0,None,None,None)\n",
    "        h1 = h\n",
    "        stack.append(head)\n",
    "        \n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            \n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "            h.next = node\n",
    "            node.prev,node.next,node.child = h,None,None\n",
    "            h = h.next\n",
    "        if h1.next:\n",
    "            h1.next.prev = None\n",
    "        return h1.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        res=head\n",
    "        tmp=[]\n",
    "        while head:\n",
    "            if head.child!=None:\n",
    "                if head.next!=None:\n",
    "                    tmp.append(head.next)\n",
    "                head.next=head.child\n",
    "                head.child=None\n",
    "                head.next.prev=head\n",
    "            if head.next!=None:\n",
    "                head=head.next\n",
    "            else:\n",
    "                if tmp!=[]:\n",
    "                    tmp1=tmp.pop()\n",
    "                    head.next=tmp1\n",
    "                    tmp1.prev=head\n",
    "                    head=head.next\n",
    "                else:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None \n",
    "        curr = head\n",
    "        while curr:\n",
    "            if curr.child:\n",
    "                n = curr.next \n",
    "                curr.next, curr.child.prev = curr.child, curr \n",
    "                curr.child = None \n",
    "                curr.next = self.flatten(curr.next)\n",
    "                while curr.next:\n",
    "                    curr = curr.next \n",
    "                if n:\n",
    "                    curr.next, n.prev = n, curr \n",
    "            else:\n",
    "                curr = curr.next \n",
    "        return head \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head \n",
    "        \n",
    "        pseudoHead = Node(None, None, head, None)\n",
    "        self.flatten_dfs(pseudoHead, head)\n",
    "\n",
    "        pseudoHead.next.prev = None\n",
    "        return pseudoHead.next\n",
    "\n",
    "    def flatten_dfs(self, pre, curr):\n",
    "        if not curr:\n",
    "            return pre \n",
    "        \n",
    "        curr.prev = pre \n",
    "        pre.next = curr \n",
    "\n",
    "        tempNext = curr.next\n",
    "        tail = self.flatten_dfs(curr, curr.child)  # flatten sub chain \n",
    "        curr.child = None\n",
    "        return self.flatten_dfs(tail, tempNext)   \n",
    "        # connect biconnection between the flattened sub chain and the root's next node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        headpre = Node(None,None,head,None)\n",
    "        self.dfs(headpre,head)\n",
    "        headpre.next.prev = None\n",
    "        return headpre.next\n",
    "    def dfs(self,pre,cur):\n",
    "        if not cur:\n",
    "            return pre\n",
    "        pre.next = cur\n",
    "        cur.prev = pre\n",
    "        tmp = cur.next\n",
    "        tail = self.dfs(cur,cur.child)\n",
    "        cur.child = None\n",
    "        return self.dfs(tail,tmp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if head.child:\n",
    "                end = dfs(head.child)\n",
    "                if head.next: # 如果有后续节点\n",
    "                    end.next = head.next \n",
    "                    end.next.prev = end \n",
    "                head.next = head.child\n",
    "                head.child.prev = head \n",
    "                head.child = None # 删除子节点\n",
    "            if head.next:\n",
    "                return dfs(head.next)\n",
    "            else:\n",
    "                return head \n",
    "        if not head: \n",
    "            return head \n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:  #这里需要判断一下，避免第一级的尾结点存在child节点的情况\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        s = deque()\n",
    "        cur = head\n",
    "        prev = None\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                if cur.next:\n",
    "                    next = cur.next\n",
    "                    next.prev = None\n",
    "                    s.append(next)\n",
    "                cur.next = cur.child\n",
    "                cur.next.prev = cur\n",
    "                cur.child = None\n",
    "            prev = cur\n",
    "            cur = cur.next\n",
    "        cur = prev\n",
    "        while s:\n",
    "            cur.next = s.pop()\n",
    "            cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        \n",
    "        find_child = head\n",
    "\n",
    "        while find_child != None:\n",
    "            if find_child.child:\n",
    "                \n",
    "                ptr = find_child\n",
    "\n",
    "                temp = ptr.next\n",
    "                child = ptr.child\n",
    "                child.prev = ptr\n",
    "                \n",
    "                while child.next:\n",
    "                    child = child.next\n",
    "\n",
    "                ptr.next = ptr.child\n",
    "\n",
    "                ptr.child = None\n",
    "                child.next = temp\n",
    "                if temp:\n",
    "                    temp.prev = child\n",
    "            \n",
    "            find_child = find_child.next\n",
    "\n",
    "            head.prev = None\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                start = end = cur.child\n",
    "                while end.next:\n",
    "                    end = end.next\n",
    "                end.next = cur.next\n",
    "                if cur.next:\n",
    "                    cur.next.prev = end\n",
    "                cur.child = None\n",
    "                cur.next = start\n",
    "                start.prev = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self,head:\"Node\")->\"Node\":\n",
    "        def dfs(node:Node)->Node:\n",
    "            cur=node\n",
    "            last=None\n",
    "            while cur:\n",
    "                next=cur.next\n",
    "                if cur.child:\n",
    "                    childLast=dfs(cur.child)\n",
    "                    next=cur.next\n",
    "                    cur.next=cur.child\n",
    "                    cur.child.prev=cur\n",
    "                    cur.child=None\n",
    "                    if next:\n",
    "                        next.prev=childLast\n",
    "                        childLast.next=next\n",
    "                    last=childLast\n",
    "                else:\n",
    "                    last=cur\n",
    "                cur=next\n",
    "            return last\n",
    "        if head==None:return None\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(head):\n",
    "            pre = None\n",
    "            while head:\n",
    "                if not head.child:\n",
    "                    pre = head\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    nxt = head.next\n",
    "                    childLast = dfs(head.child)\n",
    "                    head.next = head.child\n",
    "                    head.child.prev = head\n",
    "                    head.child = None\n",
    "                    childLast.next = nxt\n",
    "                    if nxt:\n",
    "                        nxt.prev = childLast\n",
    "                    pre = childLast\n",
    "                    head = nxt\n",
    "            return pre\n",
    "\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def link_child(node_father:'Node', node_child:'Node'):\n",
    "            if not node_child:\n",
    "                return node_father\n",
    "            node_father.next = node_child\n",
    "            node_child.prev = node_father\n",
    "\n",
    "            next_child = node_child.next\n",
    "            tail = link_child(node_child, node_child.child)\n",
    "\n",
    "            node_child.child = None\n",
    "\n",
    "            return link_child(tail, next_child)\n",
    "            \n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        tmp = Node(-1, None, None, None)\n",
    "        tmp.next = head\n",
    "        \n",
    "        link_child(tmp, head)\n",
    "        tmp.next.prev = None\n",
    "        \n",
    "        return tmp.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        s = head\n",
    "        while s:\n",
    "            if s.child:\n",
    "                nex = s.next\n",
    "                cur = s.child\n",
    "\n",
    "                s.next = cur\n",
    "                s.child = None\n",
    "                cur.prev = s\n",
    "                while cur.next:\n",
    "                    cur = cur.next\n",
    "                if nex:\n",
    "                    nex .prev = cur\n",
    "                cur.next = nex\n",
    "            s = s.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        visitor = head\n",
    "        while visitor != None:\n",
    "            if visitor.child == None:\n",
    "                visitor = visitor.next\n",
    "                continue\n",
    "            childvisitor = visitor.child\n",
    "            while childvisitor.next != None:\n",
    "                childvisitor = childvisitor.next\n",
    "            childvisitor.next = visitor.next\n",
    "            if visitor.next != None:\n",
    "                visitor.next.prev = childvisitor\n",
    "            visitor.next = visitor.child\n",
    "            visitor.child.prev = visitor\n",
    "            visitor.child = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        self.dfs(head)\n",
    "        return head\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        while node.next and not node.child:\n",
    "            node = node.next\n",
    "        \n",
    "        tail = None\n",
    "        if node.child:\n",
    "            tail = self.dfs(node.child)\n",
    "\n",
    "            temp = node.next\n",
    "            node.next = node.child\n",
    "            node.child.prev = node\n",
    "            node.child = None\n",
    "            tail.next = temp\n",
    "            if temp:\n",
    "                temp.prev = tail\n",
    "            return self.dfs(tail)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    \n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None, None\n",
    "            \n",
    "            head = tail = node\n",
    "            child = node.child\n",
    "            nex = node.next\n",
    "            node.next = None\n",
    "            node.child = None\n",
    "            \n",
    "            son_head, son_tail = dfs(child)\n",
    "            if son_head:\n",
    "                head.next = son_head\n",
    "                head.next.prev = head\n",
    "                tail = son_tail\n",
    "\n",
    "            post_head, post_tail = dfs(nex)\n",
    "            if post_head:\n",
    "                tail.next = post_head\n",
    "                tail.next.prev = tail\n",
    "                tail = post_tail\n",
    "            return head, tail\n",
    "\n",
    "        return dfs(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        curr = root\n",
    "        while curr:\n",
    "            if curr.left != None:\n",
    "                prev = curr.left\n",
    "                while prev.right:\n",
    "                    prev = prev.right\n",
    "                prev.right = curr.right\n",
    "                curr.right = curr.left\n",
    "                curr.left = None\n",
    "            curr = curr.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        \n",
    "\n",
    "        if root.left:\n",
    "            temp=root.right\n",
    "            root.right=root.left\n",
    "            root.left=None\n",
    "\n",
    "            right=root.right\n",
    "\n",
    "            while right and right.right:\n",
    "                right=right.right\n",
    "\n",
    "            right.right=temp\n",
    "        \n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def _firstorderTraversal(_root, out):\n",
    "            out.append(_root.val)\n",
    "            if _root.left:\n",
    "                out = _firstorderTraversal(_root.left, out)\n",
    "            if _root.right:\n",
    "                out = _firstorderTraversal(_root.right, out)\n",
    "            return out\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        out = _firstorderTraversal(root, [])\n",
    "        print(out)\n",
    "\n",
    "        head = root\n",
    "        for each in out[1:]:\n",
    "            head.right = TreeNode(each)\n",
    "            head.left = None\n",
    "            head = head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        def deep_search(node):\n",
    "            left_c = node.left\n",
    "            right_c = node.right\n",
    "            last_c = node\n",
    "\n",
    "            if left_c is not None:\n",
    "                node.right = left_c\n",
    "                node.left = None\n",
    "                last_c = deep_search(left_c)\n",
    "            if right_c is not None:\n",
    "                last_c.right = right_c\n",
    "                last_c = deep_search(right_c)\n",
    "            return last_c\n",
    "        if root is not None:\n",
    "            deep_search(root)\n",
    "\n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.left:\n",
    "                tmp = cur.left\n",
    "                while tmp.right:\n",
    "                    tmp = tmp.right\n",
    "                tmp.right = cur.right\n",
    "                cur.right = cur.left\n",
    "                cur.left = None\n",
    "            cur = cur.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        replace(root)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        replace(root)\n",
    "\n",
    "\n",
    "\n",
    "def replace(node:TreeNode):\n",
    "    if not node:\n",
    "        return\n",
    "    temp = node.right\n",
    "\n",
    "    if node.left != None:\n",
    "        node.right = node.left\n",
    "\n",
    "        p = node.left\n",
    "\n",
    "        if temp:\n",
    "            while p.right != None:\n",
    "                p = p.right\n",
    "            p.right = temp\n",
    "    else:\n",
    "        if temp:\n",
    "            node.right = temp\n",
    "\n",
    "    node.left = None\n",
    "\n",
    "    replace(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        \n",
    "        temp = root.right\n",
    "        root.right = root.left\n",
    "        root.left = None\n",
    "        tail = root\n",
    "        while(tail.right != None):\n",
    "            print (tail.val)\n",
    "            tail = tail.right\n",
    "        tail.right = temp\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if root is None: return \n",
    "        \n",
    "        def helper(bt):\n",
    "            left = bt.left\n",
    "            right = bt.right\n",
    "            if left:\n",
    "                tmp = left\n",
    "                while tmp.right:\n",
    "                    tmp = tmp.right\n",
    "                tmp.right = right\n",
    "            else:\n",
    "                left = right\n",
    "            bt.left = None\n",
    "            bt.right = left\n",
    "            if bt.left:\n",
    "                helper(bt.left)\n",
    "            if bt.right:\n",
    "                helper(bt.right)\n",
    "                \n",
    "        helper(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def flatten(self, root: TreeNode) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify root in-place instead.\r\n",
    "        \"\"\"\r\n",
    "\r\n",
    "        cur=root\r\n",
    "\r\n",
    "        while cur:\r\n",
    "            if cur.left:\r\n",
    "                p=cur.left\r\n",
    "                while p.right:\r\n",
    "                    p=p.right\r\n",
    "                p.right=cur.right\r\n",
    "                cur.right=cur.left\r\n",
    "                cur.left=None\r\n",
    "\r\n",
    "            cur=cur.right\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    ptr = None\n",
    "    def _flatten(self, root):\n",
    "        if root == None:\n",
    "            self.ptr.right = root\n",
    "            return\n",
    "        left_node = root.left\n",
    "        right_node = root.right\n",
    "        self.ptr.right = root\n",
    "        self.ptr = self.ptr.right\n",
    "        root.left = None\n",
    "        root.right = None\n",
    "        self._flatten(left_node)\n",
    "        self._flatten(right_node)\n",
    "\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        res = TreeNode(0)\n",
    "        self.ptr = res\n",
    "        self._flatten(root)\n",
    "        return res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        def preOrder(node):\n",
    "            if node:\n",
    "                res.append(node)\n",
    "            if node.left:\n",
    "                preOrder(node.left)\n",
    "            if node.right:\n",
    "                preOrder(node.right)\n",
    "        preOrder(root)\n",
    "        for i in range(len(res)-1):\n",
    "            res[i].left = None\n",
    "            res[i].right = res[i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            # 找左子树的最右节点\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                # 将原来的右子树接到左子树的最右边节点\n",
    "                pre.right = root.right\n",
    "                # 将左子树插入到右子树的地方\n",
    "                root.right, root.left = root.left, None\n",
    "                # 考虑下一个节点\n",
    "                root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        stack = [root]\n",
    "        prev = None\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if prev:\n",
    "                prev.right = node\n",
    "                prev.left = None\n",
    "            if node:\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "                prev = node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        # check\n",
    "        if not root: return root\n",
    "\n",
    "        # init\n",
    "        stack = [root]\n",
    "        \n",
    "        # loop\n",
    "        while len(stack):\n",
    "            curr = stack.pop()\n",
    "            if curr:\n",
    "                node_l, node_r = curr.left, curr.right\n",
    "                if node_r:  stack.append(node_r)\n",
    "                if node_l:  stack.append(node_l)\n",
    "                curr.right = stack[-1] if len(stack) else None\n",
    "                curr.left = None\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        curr = root\n",
    "        while curr:\n",
    "            if curr.left:\n",
    "                p = curr.left\n",
    "                while p.right:\n",
    "                    p = p.right\n",
    "                p.right = curr.right\n",
    "                curr.right = curr.left\n",
    "                curr.left = None\n",
    "            curr = curr.right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.helper(root)\n",
    "        \n",
    "\n",
    "    def helper(self, root):\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "\n",
    "        root.left = None\n",
    "        root.right = left\n",
    "        while root.right:\n",
    "            root = root.right\n",
    "        root.right = right\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if root.left is None:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right is not None:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.to_link(root)\n",
    "\n",
    "    def to_link(self, root):\n",
    "        if root.left is None and root.right is None:\n",
    "            return root\n",
    "\n",
    "        end = root\n",
    "        right = root.right\n",
    "        if root.left is not None:\n",
    "            end = self.to_link(root.left)\n",
    "            root.right = root.left\n",
    "            root.left = None\n",
    "\n",
    "        if right is not None:\n",
    "            end.right = right\n",
    "            end = self.to_link(right)\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None, None\n",
    "            if not node.left and not node.right:\n",
    "                return node, node\n",
    "            left_head, left_tail = helper(node.left)\n",
    "            right_head, right_tail = helper(node.right)\n",
    "            if left_head:\n",
    "                node.right = left_head\n",
    "                node.left = None\n",
    "                left_tail.right = right_head\n",
    "            else:\n",
    "                node.right = right_head\n",
    "            if right_tail:\n",
    "                return node, right_tail\n",
    "            else: \n",
    "                return node, left_tail \n",
    "\n",
    "        helper(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            res.append(root)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        for i in range(len(res) - 1):\n",
    "            res[i].right = res[i + 1]\n",
    "            res[i].left = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        left = self.traverse(node.left)\n",
    "        right = self.traverse(node.right)\n",
    "\n",
    "        if left is None:\n",
    "            left = right\n",
    "        else:\n",
    "            p = left\n",
    "            while p.right:\n",
    "                p=p.right\n",
    "            p.right=right\n",
    "\n",
    "        node.right=left\n",
    "        node.left=None\n",
    "        return node\n",
    "\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        pass\n",
    "        self.traverse(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:return None\n",
    "        tmp = root.right\n",
    "        root.right = None\n",
    "        if root.left:\n",
    "            root.right = self.flatten(root.left)\n",
    "            root.left = None\n",
    "        cur = root\n",
    "        while cur.right:\n",
    "            cur = cur.right\n",
    "        cur.right = self.flatten(tmp)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorder(self, root, ans):\n",
    "        if root:\n",
    "            ans.append(root)\n",
    "            self.preorder(root.left, ans)\n",
    "            self.preorder(root.right, ans)\n",
    "\n",
    "    def recursion(self, root):\n",
    "        ans = []\n",
    "        self.preorder(root, ans)\n",
    "        for i in range(len(ans)-1):\n",
    "            curnode, nextnode = ans[i], ans[i+1]\n",
    "            curnode.right = nextnode\n",
    "            curnode.left = None\n",
    "    \n",
    "    def iteratin(self, root):\n",
    "        if root:\n",
    "            rootlist = []\n",
    "            sta = [root]\n",
    "            while sta:\n",
    "                curnode = sta.pop()\n",
    "                rootlist.append(curnode)\n",
    "                if curnode.right:\n",
    "                    sta.append(curnode.right)\n",
    "                if curnode.left:\n",
    "                    sta.append(curnode.left)\n",
    "                \n",
    "            for i in range(len(rootlist)-1):\n",
    "                curnode, nextnode = rootlist[i], rootlist[i+1]\n",
    "                curnode.right = nextnode\n",
    "                curnode.left = None\n",
    "    def prenode(self, root):\n",
    "        if root:\n",
    "            tmp = root\n",
    "            while tmp:\n",
    "                while tmp.left:\n",
    "                    pre = tmp.left\n",
    "                    while pre.right:\n",
    "                        pre = pre.right\n",
    "                    pre.right = tmp.right\n",
    "                    tmp.right = tmp.left\n",
    "                    tmp.left = None\n",
    "                tmp = tmp.right \n",
    "    def preorderplus(self, root):\n",
    "        if root:\n",
    "            sta = [root]\n",
    "            pre = None\n",
    "            while sta:\n",
    "                cur = sta.pop()\n",
    "                if pre:\n",
    "                    pre.right = cur\n",
    "                    pre.left = None\n",
    "                if cur.right:\n",
    "                    sta.append(cur.right)\n",
    "                if cur.left:\n",
    "                    sta.append(cur.left)\n",
    "                pre = cur\n",
    "\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.recursion(root)\n",
    "        # self.iteratin(root)\n",
    "        # self.prenode(root)\n",
    "        # self.preorderplus(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root and root.left is None:\n",
    "            root = root.right\n",
    "        if root is None:\n",
    "            return\n",
    "\n",
    "        right = root.right\n",
    "        left = root.left\n",
    "        cur = left\n",
    "        while cur.right:\n",
    "            cur = cur.right\n",
    "        cur.right = right\n",
    "        root.right = left\n",
    "        root.left = None\n",
    "        self.flatten(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        lst = []\n",
    "        self.first_order(root, lst)\n",
    "\n",
    "        size = len(lst)\n",
    "        for i in range(1, size):\n",
    "            prev, cur = lst[i-1], lst[i]\n",
    "            prev.right = cur\n",
    "            prev.left = None\n",
    "\n",
    "\n",
    "\n",
    "    def first_order(self, root, lst):\n",
    "        if root == None:\n",
    "            return \n",
    "        \n",
    "        lst.append(root)\n",
    "        \n",
    "        self.first_order(root.left, lst)\n",
    "        self.first_order(root.right, lst)\n",
    "        \n",
    "        return lst\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return None\n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "\n",
    "        if root.left:\n",
    "            temp = root.right\n",
    "            root.right =  root.left\n",
    "            root.left = None\n",
    "            while root.right:\n",
    "                root=root.right\n",
    "            root.right=temp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            right1 = traverse(root.left)\n",
    "            right2 = traverse(root.right)\n",
    "            root.right =right1\n",
    "            root.left = None\n",
    "            p = root\n",
    "            while p.right:\n",
    "                p =p.right\n",
    "            p.right = right2\n",
    "            return root\n",
    "        root = traverse(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    last_node = None\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.last_node = None\n",
    "        def helper(node: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            helper(node.right)\n",
    "            helper(node.left)\n",
    "            node.right = self.last_node\n",
    "            node.left = None\n",
    "            self.last_node = node\n",
    "\n",
    "        helper(root)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
